package com.bigshen.algorithm.gTree;

public class Desc {

    /**
     *
     *  树：
     * 节点：
     *  父节点、子节点、兄弟节点
     *  根节点、叶子结点、非叶子节点
     *
     *
     *  高度： 从下往上，起点低，越往上越大
     *  深度： 从上往下，越往下越大；
     *  层： 根节点为第一层，往下依次底层
     *
     */


    /**
     *
     * 树的种类：
     * 无序树、有序树、
     * 二叉树、完全二叉树、满二叉树、红黑树、。。。
     *
     *   二叉树： 每个节点可以有两个子节点，左子节点和右子节点，但是不强制同时有两个子节点
     *
     *   满二叉树： 叶子节点全部在最底层 & 非叶子结点都有左右两个子节点
     *
     *   完全二叉树： 叶子节点全部在最底下两层 && 最后一层叶子节点全部居左 && 除了最后一层其它层的节点个数都达到了最大
     */

    /**
     *
     * 树的遍历：
     *
     * Pre-order 前序遍历：
     *      父节点 -> 左子节点 -> 右子节点    先打印父节点，然后打印左子树，最后打印右子树
     *
     * In-order 中序遍历：  任意一个节点，先打印它的左节点; 然后自己、然后右节点
     *      左节点 -> 自己 -> 右节点
     *
     * Post-order 后序遍历： 对于任意节点，先打印左、再打印右、最后打印自己
     *  先打印左子树 -> 右子树 -> 父节点
     *
     *  Level-order 从上至下，从左至右
     *
     *
     */

    /**
     *
     *  二叉树 -> 二叉查找树 BST -> 平衡二叉(查找)树 AVL树 -> 多路平衡二叉树 B树 -> 加强版多路平衡查找树 B+树
     *
     *  二叉树 Binary Tree
     *
     *  二叉查找树 BinarySearchTree :  中间节点左子树都比中间节点小，右侧节点都比中间节点大
     *
     *  平衡二叉(查找)树 AVL树 : 强平衡二叉树
     *      1. 可以使空树
     *      2. 假如不是空树，任何一个节点的左子树与右子树都是平衡二叉树，并且高度差绝对值不超过1
     *
     *  弱平衡二叉树 红黑树 RedBlackTree:
     *      1. 两种节点： 红色和黑色
     *      2. 根节点是黑色的
     *      3. 每个叶子节点都是黑色的 NIL 空节点
     *      4. 红色节点被黑色节点隔开，红色节点的子节点不能为红色节点
     *      5. 每个节点，到达其可达叶子结点的所有路径，都包含相同数目的黑色节点
     *
     */
}
